package org.zlb.algorithm.sort;

/**
 * 归并排序
 *
 * @author zhoulingbo
 * @date 2021/7/14 12:45
 */
public class MergeSort extends AbstractSort{

    @Override
    public void sort(int[] arr) {
        int[] temps = new int[arr.length];
        sort(arr, 0, arr.length - 1, temps);
    }

    void sort(int[] arr, int low, int high, int[] temps) {
        int middle = (high + low) / 2;
        if (low < high) {
            sort(arr, low, middle, temps);
            sort(arr, middle+1, high, temps);
            merge(arr, low, middle, high, temps);
        }
    }

    void merge(int[] arr, int low, int middle, int high, int[] temps) {
        int i = low;
        int j = middle + 1;
        int k = low;
        while (i <= middle && j <= high) {
            if (compare(arr[i], arr[j]) <= 0) {
                temps[k++] = arr[i++];
            } else {
                temps[k++] = arr[j++];
            }

        }

        while (i <= middle) {
            temps[k++] = arr[i++];
        }

        while (j <= high) {
            temps[k++] = arr[j++];
        }

        k = low;
        while (k <= high) {
            arr[k] = temps[k];
            k ++;
        }
    }

}
